๐Ÿ‘ฉโ€๐Ÿ’ป 1260. DFS์™€ BFS

@Seongukbaek Posted December 29, 2021 ยท Updated December 29, 2021 ยท 5 min read

๋ฌธ์ œ

๊ทธ๋ž˜ํ”„๋ฅผ DFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ์™€ BFS๋กœ ํƒ์ƒ‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ, ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ •์ ์ด ์—ฌ๋Ÿฌ ๊ฐœ์ธ ๊ฒฝ์šฐ์—๋Š” ์ •์  ๋ฒˆํ˜ธ๊ฐ€ ์ž‘์€ ๊ฒƒ์„ ๋จผ์ € ๋ฐฉ๋ฌธํ•˜๊ณ , ๋” ์ด์ƒ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ์ ์ด ์—†๋Š” ๊ฒฝ์šฐ ์ข…๋ฃŒํ•œ๋‹ค. ์ •์  ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€์ด๋‹ค.

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 1,000), ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ M(1 โ‰ค M โ‰ค 10,000), ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•  ์ •์ ์˜ ๋ฒˆํ˜ธ V๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ M๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ„์„ ์ด ์—ฐ๊ฒฐํ•˜๋Š” ๋‘ ์ •์ ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์–ด๋–ค ๋‘ ์ •์  ์‚ฌ์ด์— ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ฐ„์„ ์ด ์žˆ์„ ์ˆ˜ ์žˆ๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ๊ฐ„์„ ์€ ์–‘๋ฐฉํ–ฅ์ด๋‹ค.

์ถœ๋ ฅ

  • ์ฒซ์งธ ์ค„์— DFS๋ฅผ ์ˆ˜ํ–‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ, ๊ทธ ๋‹ค์Œ ์ค„์—๋Š” BFS๋ฅผ ์ˆ˜ํ–‰ํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. V๋ถ€ํ„ฐ ๋ฐฉ๋ฌธ๋œ ์ ์„ ์ˆœ์„œ๋Œ€๋กœ ์ถœ๋ ฅํ•˜๋ฉด ๋œ๋‹ค.

๐Ÿ“ Logic

class Graph { public ArrayList<ArrayList<Integer>> graph; public boolean[] visited = new boolean[1001]; public StringBuilder path = new StringBuilder(); }
  • graph๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ๋™์  2์ฐจ์› ๋ฐฐ์—ด
  • ์ •์ ์— ๋Œ€ํ•œ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€ ์ €์žฅ์„ ์œ„ํ•œ boolean ๋ฐฐ์—ด
  • DFS ์™€ BFS ์˜ ๋ฐฉ๋ฌธ ์ˆœ์„œ๋ฅผ ์ €์žฅํ•˜๋Š” stringBuilder
public void dfs(int start) { if (!visited[start]) { path.append(start); path.append(" "); visited[start] = true; for (int i = 0; i < graph.get(start).size(); i++) { if (!visited[graph.get(start).get(i)]) { this.dfs(graph.get(start).get(i)); } } } }
  • ์žฌ๊ท€ ํ˜ธ์ถœ์„ ์ด์šฉํ•œ DFS ๊ตฌํ˜„
public void bfs(int start) { Queue<Integer> q = new LinkedList<>(); q.offer(start); visited[start] = true; path.append("\n"); path.append(start); while (!q.isEmpty()) { int cur = q.poll(); for (int i = 0; i < graph.get(cur).size(); i++) { if (!visited[graph.get(cur).get(i)]) { visited[graph.get(cur).get(i)] = true; path.append(" "); path.append(graph.get(cur).get(i)); q.offer(graph.get(cur).get(i)); } } } }
  • Queue๋ฅผ ์ด์šฉํ•œ BFS ๊ตฌํ˜„
for (int i = 1; i <= n; i++) { Collections.sort(g.graph.get(i)); }
  • ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ์ •์ ๋ถ€ํ„ฐ ๋ฐฉ๋ฌธํ•˜๋ผ๋Š” ๋ฌธ์ œ์˜ ์กฐ๊ฑด์„ ์œ„ํ•œ ์ •๋ ฌ

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Graph { public ArrayList<ArrayList<Integer>> graph; public boolean[] visited = new boolean[1001]; public StringBuilder path = new StringBuilder(); public Graph(int size) { this.graph = new ArrayList<ArrayList<Integer>>(); for (int i = 0; i < size + 1; i++) { graph.add(new ArrayList<Integer>()); } } public void DoubleAdd(int x, int y) { graph.get(x).add(y); graph.get(y).add(x); } public void dfs(int start) { if (!visited[start]) { path.append(start); path.append(" "); visited[start] = true; for (int i = 0; i < graph.get(start).size(); i++) { if (!visited[graph.get(start).get(i)]) { this.dfs(graph.get(start).get(i)); } } } } public void bfs(int start) { Queue<Integer> q = new LinkedList<>(); q.offer(start); visited[start] = true; path.append("\n"); path.append(start); while (!q.isEmpty()) { int cur = q.poll(); for (int i = 0; i < graph.get(cur).size(); i++) { if (!visited[graph.get(cur).get(i)]) { visited[graph.get(cur).get(i)] = true; path.append(" "); path.append(graph.get(cur).get(i)); q.offer(graph.get(cur).get(i)); } } } } public StringBuilder getPath() { return path; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int start = sc.nextInt(); Graph g = new Graph(n); for (int i = 0; i < m; i++) { int a = sc.nextInt(); int b = sc.nextInt(); g.DoubleAdd(a,b); } for (int i = 1; i <= n; i++) { Collections.sort(g.graph.get(i)); } Arrays.fill(g.visited,false); g.dfs(start); Arrays.fill(g.visited,false); g.bfs(start); System.out.print(g.getPath().toString()); sc.close(); } }

โœ๏ธ Review

  • ์„ฑ๊ณตํ–ˆ์—ˆ๋‹ค๊ฐ€ ์‹คํŒจ๋กœ ์žฌ์ฑ„์ ๋˜์–ด ์ด๋ฒˆ ๊ธฐํšŒ์— JAVA ๋กœ ๋ณ€ํ™˜ํ•˜๋ฉด์„œ ๋‹ค์‹œ ํ‘ผ ๋ฌธ์ œ
  • class Graph ์™€ ๊ฐ™์ด ํด๋ž˜์Šค๋ฅผ ๋งŒ๋“œ๋Š” ๋ฐฉ์‹์„ ์ด์šฉํ•ด Graph์™€ ๊ด€๋ จ๋œ ์ฒ˜๋ฆฌ๋“ค์„ ์ตœ๋Œ€ํ•œ ํด๋ž˜์Šค ๋‚ด๋ถ€์—์„œ ๊ตฌํ˜„ํ•˜๋„๋ก ํ–ˆ๋‹ค.
  • ์ฒ˜์Œ์—๋Š” int[] path ๋ฅผ ๋‘ ๋ฒˆ ์‚ฌ์šฉํ•˜์—ฌ DFS ์˜ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , BFS ์˜ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ–ˆ์—ˆ๋Š”๋ฐ, ๋‹ค๋ฅธ ๋ฐฉ์‹์„ ์ฐพ์•„๋ณด๋‹ค๊ฐ€ StringBuilder ํด๋ž˜์Šค๋ผ๋Š” ๊ฒƒ์„ ๋ฐœ๊ฒฌํ•˜์—ฌ ์ด๋ฅผ ์‚ฌ์šฉํ•ด๋ณด์•˜๋‹ค.

    • StringBuilder : ์—ฌ๋Ÿฌ ๋ฌธ์ž์—ด์„ ๋ถ™์ด๋Š” ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๊ฒฝ์šฐ ํšจ์œจ์ ์ธ ํด๋ž˜์Šค๋กœ, ํ•ด๋‹น ๋ฌธ์ œ์—์„œ๋Š” ์ •์ ์˜ ๋ฐฉ๋ฌธ ์ˆœ์„œ๋ฅผ ์ˆœ์ฐจ์ ์œผ๋กœ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉํ–ˆ๋‹ค.
  • ๊ตฌํ˜„ ๋ฐฉ์‹์€ ํ‹€๋ฆฐ ๊ฒƒ์ด ์—†์–ด๋ณด์˜€๋Š”๋ฐ ์ž๊พธ ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค ๊ฐ€ ๋– ์„œ ํ™”๊ฐ€ ๋‚  ๋•Œ ์ฆˆ์Œ ๋ฐœ๊ฒฌํ•œ ํ•œ ๋ฐ˜๋ก€๋กœ ๋””๋ฒ„๊น…์„ ํ•ด๋ณด๋‹ˆ, ์ •๋ ฌ ์‹œ ๋ฐ˜๋ณต ํšŸ์ˆ˜๊ฐ€ 1๋ฒˆ ๋ชจ์ž๋ž€ ๊ฒƒ์ด์—ˆ๋‹ค.
  • ์ถ”๊ฐ€๋กœ, visited ๋ฐฐ์—ด์„ int ๋กœ ํ•œ ๊ฒฝ์šฐ์™€ boolean ์œผ๋กœ ํ•œ ๊ฒฝ์šฐ ์‹œ๊ฐ„๊ณผ ๋ฉ”๋ชจ๋ฆฌ ์ฐจ์ด๊ฐ€ ์กด์žฌํ–ˆ๋Š”๋ฐ, boolean ์˜ ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ๋” ์ ๊ณ  ์‹œ๊ฐ„์ด ๊ฐ์†Œํ–ˆ์„๊ฑฐ๋ž€ ์˜ˆ์ƒ๊ณผ๋Š” ๋‹ฌ๋ฆฌ, ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ์ฆ๊ฐ€ํ•œ ๊ฒƒ์„ ํ™•์ธํ–ˆ๋‹ค. ์•„์ง ์ด์œ ๋Š” ์ž˜ ๋ชจ๋ฅด๊ฒ ๋‹ค ..

๐Ÿ“• ์ถœ์ฒ˜

https://www.acmicpc.net/problem/1260

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€